import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.Random;
/**
 * This class is SkipList
 * @author ldong
 *
 * @param <T>
 */
public class SkipList<T extends Comparable<? super T>>
//public class SkipList<T extends Comparable<? extends T>>

{
	  /**
	   * Private inner class for Nodes
	   */
	   private class Node<T extends Comparable<? super T>>
	   {
		 public Node<T> next;
		 public Node<T> down;
		 public T data;
		 /**
		  * Constructor which sets the next and down nodes to null   
		  */
		 public Node()
		 {
			 this(null);
		 }
		 
		 public Node(T data)
		 {
			 next = null;
			 down = null;
			 this.data = data;
		 }
		 
		 /**
		  * Sets the data
		  * @param data
		  */
		 public void setData(T data)
		 {
			 this.data = data;
		 }
		 
		 /**
		  * Get data
		  * @return
		  */
		 public T getData()
		 {
			 return data;
		 }
		 
		 /**
		  * Return if it has next data
		  * @return
		  */
		 public boolean hasNext()
		 {
			 return next == null;
		 }
		 
		 public String toString()
		 {
		    return " <"+ data + ">";
		 }
		 
	   }
	   
	   /**
	    * Private variables
	    */
	   private int nodeLevel;
	   /**
	    * Where actual stores the data
	    */
	   private Node<T>[] root;
	   
	   private int maxLevel;
	   private int currentMax;  // currentMaxLevel
	   private int bottomLevel;
	   private int size;
	   /**
	    * Constructor for SkipList
	    * set the bottom level to 0 level
	    */
	   public SkipList()
	   {
		   /* The default max level is 10, from 0 - 9 */
		   this(10);
	   }
	   
	   /**
	    * Set up the max Level of the SkipLists
	    * @param maxLevel
	    */
	   public SkipList(int maxLevel)
	   {
		   this.maxLevel = maxLevel;
		   
		   size = 0;
		   nodeLevel = 0;
		   currentMax = 0;
		   bottomLevel = 0;

		   root = new Node[maxLevel];
		   
		   for(int i = 0; i<maxLevel; i++)
			   root[i]=null;
	   }
	   
	   
	   
	   public void add(T data)
	   {
		   /* 
		    * If not valid, ignore it
		    */
		   if(data == null)
			   return;
		   /*
		    * else, continue
		    */
		   
/*		   size++;
           Node<T> target = new Node<T>(data);
           // testing 
           System.out.println(target+" target data runs");
           System.out.println(""+ root.length);
           
           if(root[bottomLevel] == null)
           {
        	   System.out.println("BL is Null");
           }
           
           root[bottomLevel] = new Node<T>();
           
           if(root[bottomLevel].next == null)
           {
        	   System.out.println("BL next is Null");
           }
           
           root[bottomLevel].next = target;
           
           if(root[0].hasNext() == true)
           {
        	   System.out.println("It has next");
           }
           else
           {
        	   System.out.println("It has NO next");
           }
*/           
           Node<T> target = new Node<T>(data);

           if(isEmpty())
           {
        	   size++;
        	   root[bottomLevel]= new Node<T>();
        	   root[bottomLevel].next  = target;
               while(odds())
               {
            	   nodeLevel++;
        		   root[nodeLevel] = new Node<T>();
            	   if(root[nodeLevel].next == null)
                   {
            		   // working on it later
            		   Node<T> node = new Node<T>(data);
//            		   root[nodeLevel] = new Node<T>();
            		   root[nodeLevel].next = node;
            		   node.down = target;
                   }
            	   else // if it is not null, which means it has more than 1 node
            	   {
            		   Node<T> current = new Node<T>();
            		   Node<T> next    = new Node<T>();
            		   //assign from the start
            		   current = root[nodeLevel].next;
            		   next    = current.next;
            		   
            		   while(current.getData().compareTo(target.getData())<0)
            		   {
            			   current = current.next;
            		   }
            		   if(current.next != null)
            		   {
            			   next = current.next;
            		   }
            		   /* assign target to current.next
            		    * and still holds the data of current.next.next 
            		    */
            		   current.next = target;
            		   target.next = next.next;
            	   }// end of if else
               }// end of while
           }
           else
           {
        	   if(root[maxLevel].getData().compareTo(target.getData()) > 0)
        	   {
        		   
        		   
        		   
        		   
        		   
        		   
        	   }// end of if
        	   else if(root[maxLevel].getData().compareTo(target.getData()) <= 0)
        	   {
        		   
        	   }// end of else if
           }
           
           while(odds())
           {
        	  System.out.println("Running the odds to create a new LinkedList " + nodeLevel);
     		  nodeLevel++;
    		  root[nodeLevel] = new Node<T>();

     		  Node<T> parent = new Node<T>();
     		  parent.down = target;
     		  root[nodeLevel].next = parent;
           }
           
	   }
	   
	   /**
	    * Find method
	    * @param target
	    * @return
	    */
	   public boolean search(T key)
	   {
		   return true;
	   }
	   
	   /**
	    * Delete Method
	    */
	   
	   public boolean isEmpty()
	   {
//		   return root[bottomLevel] == null;
		   return 0 == size;
	   }
	   
	   
	   /**
	    * toString method overriding
	    */
	   public String toString()
	   {
		   return "Working on it";
	   }
	   
	   
		/**
		 * Helper method which calculates out the odds
		 * if true, move it up to make a new skiplist
		 * otherwise, ignore it.
		 * @return
		 */
		private boolean odds()
		{
			Random rand = new Random(); 
			return rand.nextBoolean();		
		}
	   
}
